package week_six;

public class EditDistance_72 {
    public int minDistance(String word1, String word2) {
        //f[i][j] word1[1...i]与word2[1...j]的编辑距离
        //f[i][j] = min(f[i][j-1]+1(插入),f[i-1][j]+1（删除）,f[i][j]+eq)
        int m = word1.length();
        int n = word2.length();
        word1 = " " + word1;
        word2 = " " + word2;
        int[][] f = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) f[i][0] = i;
        for (int j = 0; j <= n; j++) f[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = Math.min(Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1), f[i - 1][j - 1] + (word1.charAt(i) == word2.charAt(j) ? 0 : 1));
                System.out.println(i + " " + j + " : " + f[i][j]);
            }
        }
        return f[m][n];
    }
}
